|
The Boyer-Moore Vote Algorithm solves the majority vote problem in linear time and logarithmic space . The majority vote problem is to determine in any given sequence of choices whether there is a choice with more occurrences than all the others, and if so, to determine this choice. Mathematically, given a finite sequence (length n) of numbers, the object is to find the majority number defined as the number that appears more than ⌊ n/2 ⌋ times. ==Description== The algorithm is carried out in two steps: 1. Eliminate all elements except one. Iterating through the array of numbers, maintain a current candidate and a counter initialized to 0. With the current element x in iteration, update the counter and (possibly) the candidate: If the counter is 0, set the current candidate to x and the counter to 1. If the counter is not 0, increment or decrement the counter based on whether x is the current candidate. 2. Determine if the remaining element is a valid majority element. With the candidate acquired in step 1, iterate through the array of numbers and count its occurrences. Determine if the result is more than half of the sequence's length. If so, the candidate is the majority. Otherwise, the sequence doesn't contain a majority. Note that the counter can be a maximum of which requires space. In practice however a constant number of bits should suffice as a bit counter can go upto which is large enough for any practical computation. The time complexity remains , even considering the amount of time it takes to increment the counter because it can be incremented in constant amortized time. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Boyer–Moore majority vote algorithm」の詳細全文を読む スポンサード リンク
|